HPI5: Delivering Messages // Advanced

Courier Carrie is delivering messages from the capital to the surrounding castles. The N castles in the kingdom (including the capital castle and conveniently numbered 1 to N) are connected by roads such that there exists exactly one path from any castle to any other castle. Carrie can only traverse these roads. Each castle, including the capital, has M_i messages to be delivered to it. Carrie is very picky about the way she delivers her messages. She will only travel to a castle if it still has at least one message to be delivered, and once there, she will deliver exactly one message. Carrie starts her journey at the capital castle, denoted by C, and must end her journey at the capital as well, delivering a message when she arrives. Given these conditions, what is the maximum number of messages Carrie can deliver?

1 <= N <= 10,000
1 <= M_i <= 10,000
1 <= C <= N

Input Format

Line 1: N, the number of castles
Line 2: M_i of each castle, separated by spaces
Lines 3...N+1: Each line contains two space-separated integers denoting a road between those two castles
Line N+2: C, the number of the capital castle

Sample Input

4
1 2 2 5
4 1
2 1
3 2
2

Output Format

Line 1: The maximum number of messages Carrie can deliver

Sample Output

4